package org.company.earth.arithmetic;

import java.util.List;

/**
 * 构建大顶堆 --》 swap(0,length) --》重新构建大顶堆(0,length-1)
 * length --> 当前元素数量
 * @author hucw
 *
 * @param <T>
 */
public class HeapSort<T> extends BaseSort<T> {

    /**
     * 不稳定算法
     * nlogn
     */
    @Override
    public void sort(List<T> list) {
        //构建大顶堆
        this.buildTree(list);
        int length = list.size();
        while(length > 1) {
            this.swap(list, 0, --length);
            this.heap(list, 0, length-1);
        }
    }
    
    private int leftChild(int p) {
        return 2*p+1;
    }
    
    private int rightChild(int p) {
        return 2*p+2;
    }
    
    /**
     * 调整大顶堆
     * @param list
     * @param p
     * @param end
     */
    private void heap(List<T> list,int p,int end) {
        int left,right,next;
        while((left=this.leftChild(p)) < end + 1) {
            next = left;
            right = this.rightChild(p);
            if(right <= end && gt(list.get(right),list.get(left))) {
                next = right;
            }
            if(gt(list.get(next),list.get(p))) {
                this.swap(list, p, next);
                p = next;
            } else {
                break;
            }
        }
    }
    
    /**
     * 构建大顶堆
     * @param list
     */
    private void buildTree(List<T> list) {
        int length = list.size();
        int leaf = length > 1 ? length/2 - 1 : 0;
        while(leaf >= 0) {
            this.heap(list, leaf, length-1);
            leaf--;
        }
    }
    
    public static void main(String[] args) {
        
    }
}
